{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "    @file Sklearn\n",
    "    @description Decision Tree By Sklearn Using Entropy\n",
    "    @author Synhard\n",
    "    @tel 13001321080\n",
    "    @id 21126338\n",
    "    @email 823436512@qq.com\n",
    "    @date 2021-09-24 18:03\n",
    "    @version 1.0\n",
    "\"\"\"\n",
    "import matplotlib\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import random\n",
    "\n",
    "from matplotlib import pyplot as plt\n",
    "from sklearn.metrics import confusion_matrix\n",
    "\n",
    "matplotlib.rcParams['font.family'] = 'SimHei'  # 用来正常显示中文\n",
    "plt.rcParams['axes.unicode_minus'] = False  # 用来正常显示负号\n",
    "\n",
    "decisionNode = dict(boxstyle=\"sawtooth\", fc=\"0.8\")\n",
    "leafNode = dict(boxstyle=\"round4\", fc=\"0.8\")\n",
    "arrow_args = dict(arrowstyle=\"<-\")\n",
    "random.seed(0)\n",
    "\n",
    "\n",
    "def train_test_split(df, test_size):\n",
    "    if isinstance(test_size, float):\n",
    "        test_size = round(test_size * len(df))\n",
    "\n",
    "    indices = df.index.tolist()\n",
    "    test_indices = random.sample(population=indices, k=test_size)\n",
    "\n",
    "    test_df = df.loc[test_indices]\n",
    "    train_df = df.drop(test_indices)\n",
    "\n",
    "    return train_df, test_df\n",
    "\n",
    "\n",
    "def check_purity(data):\n",
    "    label_column = data[:, -1]\n",
    "    unique_classes = np.unique(label_column)\n",
    "\n",
    "    if len(unique_classes) == 1:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "\n",
    "def classify_data(data):\n",
    "    label_column = data[:, -1]\n",
    "    unique_classes, counts_unique_classes = np.unique(label_column, return_counts=True)\n",
    "\n",
    "    index = counts_unique_classes.argmax()\n",
    "    classification = unique_classes[index]\n",
    "\n",
    "    return classification\n",
    "\n",
    "\n",
    "def get_potential_splits(data):\n",
    "    potential_splits = {}\n",
    "    _, n_columns = data.shape\n",
    "    for column_index in range(n_columns - 1):\n",
    "        potential_splits[column_index] = []\n",
    "        values = data[:, column_index]\n",
    "        unique_values = np.unique(values)\n",
    "\n",
    "        for index in range(len(unique_values)):\n",
    "            if index != 0:\n",
    "                current_value = unique_values[index]\n",
    "                previous_value = unique_values[index - 1]\n",
    "                potential_split = (current_value + previous_value) / 2\n",
    "\n",
    "                potential_splits[column_index].append(potential_split)\n",
    "\n",
    "    return potential_splits\n",
    "\n",
    "\n",
    "def split_data(data, split_column, split_value):\n",
    "    split_column_values = data[:, split_column]\n",
    "\n",
    "    data_below = data[split_column_values <= split_value]\n",
    "    data_above = data[split_column_values > split_value]\n",
    "\n",
    "    return data_below, data_above\n",
    "\n",
    "\n",
    "def calculate_entropy(data):\n",
    "    label_column = data[:, -1]\n",
    "    _, counts = np.unique(label_column, return_counts=True)\n",
    "\n",
    "    probabilities = counts / counts.sum()\n",
    "    entropy = sum(probabilities * -np.log2(probabilities))\n",
    "\n",
    "    return entropy\n",
    "\n",
    "\n",
    "def calculate_overall_entropy(data_below, data_above):\n",
    "    n = len(data_below) + len(data_above)\n",
    "    p_data_below = len(data_below) / n\n",
    "    p_data_above = len(data_above) / n\n",
    "\n",
    "    overall_entropy = (p_data_below * calculate_entropy(data_below)\n",
    "                       + p_data_above * calculate_entropy(data_above))\n",
    "\n",
    "    return overall_entropy\n",
    "\n",
    "\n",
    "def determine_best_split(data, potential_splits):\n",
    "    overall_entropy = 1000\n",
    "    best_split_column = 0\n",
    "    best_split_value = 0\n",
    "    for column_index in potential_splits:\n",
    "        for value in potential_splits[column_index]:\n",
    "            data_below, data_above = split_data(data, split_column=column_index, split_value=value)\n",
    "            current_overall_entropy = calculate_overall_entropy(data_below, data_above)\n",
    "\n",
    "            if current_overall_entropy <= overall_entropy:\n",
    "                overall_entropy = current_overall_entropy\n",
    "                best_split_column = column_index\n",
    "                best_split_value = value\n",
    "\n",
    "    return best_split_column, best_split_value\n",
    "\n",
    "\n",
    "def decision_tree_algorithm(df, counter=0, min_samples=2, max_depth=4):\n",
    "    if counter == 0:\n",
    "        global COLUMN_HEADERS\n",
    "        COLUMN_HEADERS = df.columns\n",
    "        data = df.values\n",
    "    else:\n",
    "        data = df\n",
    "    if (check_purity(data)) or (len(data) < min_samples) or (counter == max_depth):\n",
    "        classification = classify_data(data)\n",
    "\n",
    "        return classification\n",
    "    else:\n",
    "        counter += 1\n",
    "\n",
    "        potential_splits = get_potential_splits(data)\n",
    "        split_column, split_value = determine_best_split(data, potential_splits)\n",
    "\n",
    "        data_below, data_above = split_data(data, split_column, split_value)\n",
    "        feature_name = COLUMN_HEADERS[split_column]\n",
    "        question = \"{} <= {}\".format(feature_name, split_value)\n",
    "        sub_tree = {question: []}\n",
    "        yes_answer = decision_tree_algorithm(data_below, counter, min_samples, max_depth)\n",
    "        no_answer = decision_tree_algorithm(data_above, counter, min_samples, max_depth)\n",
    "        if yes_answer == no_answer:\n",
    "            sub_tree = yes_answer\n",
    "        else:\n",
    "            sub_tree[question].append(yes_answer)\n",
    "            sub_tree[question].append(no_answer)\n",
    "\n",
    "        return sub_tree\n",
    "\n",
    "\n",
    "def classify_example(example, tree):\n",
    "    question = list(tree.keys())[0]\n",
    "    feature_name, comparison_operator, value = question.split(\" \")\n",
    "    if example[feature_name] <= float(value):\n",
    "        answer = tree[question][0]\n",
    "    else:\n",
    "        answer = tree[question][1]\n",
    "\n",
    "    if not isinstance(answer, dict):\n",
    "        return answer\n",
    "    else:\n",
    "        residual_tree = answer\n",
    "        return classify_example(example, residual_tree)\n",
    "\n",
    "\n",
    "def calculate_accuracy(df, tree):\n",
    "    df[\"classification\"] = df.apply(classify_example, args=(tree,), axis=1)\n",
    "    df[\"classification_correct\"] = df[\"classification\"] == df[\"target\"]\n",
    "    accuracy = df[\"classification_correct\"].mean()\n",
    "\n",
    "    return accuracy\n",
    "\n",
    "\n",
    "def getNumLeafs(myTree):\n",
    "    numLeafs = 0\n",
    "    firstStr = list(myTree.keys())[0]\n",
    "    secondDict = myTree[firstStr]\n",
    "    for obj in secondDict:\n",
    "        if type(obj).__name__ == 'dict':\n",
    "            # nodes\n",
    "            numLeafs += getNumLeafs(obj)\n",
    "        else:\n",
    "            numLeafs += 1\n",
    "    return numLeafs\n",
    "\n",
    "\n",
    "def getTreeDepth(myTree):\n",
    "    maxDepth = 0\n",
    "    firstStr = list(myTree.keys())[0]\n",
    "    secondDict = myTree[firstStr]\n",
    "    for obj in secondDict:\n",
    "        if type(obj).__name__ == 'dict':\n",
    "            thisDepth = 1 + getTreeDepth(obj)\n",
    "        else:\n",
    "            thisDepth = 1\n",
    "        if thisDepth > maxDepth: maxDepth = thisDepth\n",
    "    return maxDepth\n",
    "\n",
    "\n",
    "def plotNode(nodeTxt, centerPt, parentPt, nodeType):\n",
    "    createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',\n",
    "                            xytext=centerPt, textcoords='axes fraction',\n",
    "                            va=\"center\", ha=\"center\", bbox=nodeType, arrowprops=arrow_args)\n",
    "\n",
    "\n",
    "def plotMidText(cntrPt, parentPt, txtString):\n",
    "    xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]\n",
    "    yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]\n",
    "    createPlot.ax1.text(xMid, yMid, txtString, va=\"center\", ha=\"center\", rotation=30)\n",
    "\n",
    "\n",
    "def plotTree(myTree, parentPt, nodeTxt):\n",
    "    numLeafs = getNumLeafs(myTree)\n",
    "    firstStr = list(myTree.keys())[0]\n",
    "    cntrPt = (plotTree.xOff + (2 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)\n",
    "    plotMidText(cntrPt, parentPt, nodeTxt)\n",
    "    plotNode(firstStr, cntrPt, parentPt, decisionNode)\n",
    "    secondDict = myTree[firstStr]\n",
    "    plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD\n",
    "    for i in range(0, len(secondDict)):\n",
    "        if type(secondDict[i]).__name__ == 'dict':\n",
    "            if i == 0:\n",
    "                plotTree(secondDict[i], cntrPt, \"Y\")  # 递归\n",
    "            else:\n",
    "                plotTree(secondDict[i], cntrPt, \"N\")  # 递归\n",
    "        else:\n",
    "            plotTree.xOff = plotTree.xOff + 1.1 / plotTree.totalW\n",
    "            plotNode(secondDict[i], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)\n",
    "            if i == 0:\n",
    "                plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, \"Y\")  # 递归\n",
    "            else:\n",
    "                plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, \"N\")  # 递归\n",
    "\n",
    "    plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD\n",
    "\n",
    "\n",
    "def createPlot(myTree):\n",
    "    fig = plt.figure(1, facecolor='white', figsize=(8, 8))\n",
    "    fig.clf()\n",
    "    axprops = dict(xticks=[], yticks=[])\n",
    "    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)\n",
    "    plotTree.totalW = float(getNumLeafs(myTree))\n",
    "    plotTree.totalD = float(getTreeDepth(myTree))\n",
    "    plotTree.xOff = -1.5 / plotTree.totalW\n",
    "    plotTree.yOff = 1.1\n",
    "    plotTree(myTree, (0.5, 1.0), '')\n",
    "    plt.show()\n",
    "\n",
    "\n",
    "def prediction(decisontree, row):\n",
    "    if isinstance(decisontree, float):\n",
    "        return decisontree\n",
    "    root = list(decisontree.keys())[0]\n",
    "    attr = root.split(\" <= \")[0]\n",
    "    value = root.split(\" <= \")[1]\n",
    "    if float(row.get(attr)) <= float(value):\n",
    "        return prediction(decisontree.get(root)[0], row)\n",
    "    else:\n",
    "        return prediction(decisontree.get(root)[1], row)\n",
    "    pass\n",
    "\n",
    "\n",
    "def testTree(decisontree, dataSet):\n",
    "    testmemory = []\n",
    "    label = []\n",
    "    TP = 0\n",
    "    FP = 0\n",
    "    TN = 0\n",
    "    FN = 0\n",
    "    rowDict = []\n",
    "    for i in range(1, dataSet.shape[0]):\n",
    "        dict = {}\n",
    "        for j in range(0, dataSet[0].shape[0]):\n",
    "            dict[dataSet[0][j]] = dataSet[i][j]\n",
    "\n",
    "        rowDict.append(dict)\n",
    "\n",
    "    for row in rowDict:\n",
    "        label.append(row['target'])\n",
    "        testmemory.append(str(prediction(decisontree, row)))\n",
    "        pass\n",
    "\n",
    "    for i in range(0, len(rowDict)):\n",
    "        if (testmemory[i] == '1.0') and (label[i] == '1.0'):  # testmemory为预测 label为实际\n",
    "            TP += 1\n",
    "        elif (testmemory[i] == '1.0') and (label[i] == '0.0'):\n",
    "            FP += 1\n",
    "        elif (testmemory[i] == '0.0') and (label[i] == '0.0'):\n",
    "            TN += 1\n",
    "        elif (testmemory[i] == '0.0') and (label[i] == '1.0'):\n",
    "            FN += 1\n",
    "\n",
    "    print('TP:%d' % TP)  # 真阳性\n",
    "    print('FP:%d' % FP)  # 假阳性\n",
    "    print('TN:%d' % TN)  # 真阴性\n",
    "    print('FN:%d' % FN)  # 假阴性\n",
    "\n",
    "    cm = confusion_matrix(label, testmemory, labels=[\"0.0\", \"1.0\"])\n",
    "    plt.rc('figure', figsize=(8, 8))\n",
    "    plt.matshow(cm, cmap=plt.cm.cool)  # 背景颜色\n",
    "    plt.colorbar()  # 颜色标签\n",
    "    # 内部添加图例标签\n",
    "    for x in range(len(cm)):\n",
    "        for y in range(len(cm)):\n",
    "            plt.annotate(cm[x, y], xy=(y, x), horizontalalignment='center', verticalalignment='center')\n",
    "    plt.ylabel('True Label')\n",
    "    plt.xlabel('Predicted Label')\n",
    "    plt.title('decision_tree')\n",
    "    plt.savefig(r'confusion_matrix')\n",
    "    plt.show()\n",
    "\n",
    "\n",
    "# 主函数\n",
    "if __name__ == '__main__':\n",
    "    df = pd.read_excel(\"heart.xlsx\")\n",
    "    train_df, test_df = train_test_split(df, test_size=0.3)\n",
    "    data = train_df.values\n",
    "    decisionTree = decision_tree_algorithm(train_df, max_depth=5)\n",
    "    test_data = list(test_df.values)\n",
    "    test_data.insert(0, list(test_df.columns))\n",
    "    testTree(decisionTree, np.array(test_data))\n",
    "    createPlot(decisionTree)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}